/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30



␈↓ ↓H␈↓α␈↓ ∧PROBLEMS OF ARTIFICIAL INTELLIGENCE

␈↓ ↓H␈↓1. Creativity

␈↓ ↓H␈↓␈↓ α_Machines␈α∪will␈α∩never␈α∪be␈α∩able␈α∪to␈α∪compete␈α∩with␈α∪humans␈α∩intellectually␈α∪until␈α∪they␈α∩exhibit
␈↓ ↓H␈↓something␈α
comparable␈α
to␈α
human␈α
creativity.␈α
 However,␈α
all␈α
the␈α
literature␈α
dealing␈α
with␈α
creativity␈α
that
␈↓ ↓H␈↓I␈αknow␈αabout␈αtakes␈αa␈αrather␈αmystical␈αattitude␈αand␈αdoesn't␈αseriously␈αtry␈αto␈αanalyze␈αcreativity␈α-␈αjust
␈↓ ↓H␈↓admire it.  Admiration is fine, but won't result in computer programs.

␈↓ ↓H␈↓␈↓ α_Our␈αfirst␈αstrategy␈αis␈αto␈αseek␈α
what␈αmight␈αbe␈αcalled␈α"easy␈αcreativity"␈αrather␈α
than␈αimmediately
␈↓ ↓H␈↓try␈α⊃to␈α⊂duplicate␈α⊃Einstein␈α⊂or␈α⊃Shakespeare.␈α⊃ To␈α⊂this␈α⊃end␈α⊂we␈α⊃tentatively␈α⊂define␈α⊃creativity␈α⊃as␈α⊂the
␈↓ ↓H␈↓introduction␈αof␈αconcepts␈αinto␈αthe␈α
solution␈αof␈αa␈αproblem␈αthat␈α
are␈αnot␈αinvolved␈αin␈αthe␈α
statement␈αof
␈↓ ↓H␈↓the␈αproblem␈αor␈α
in␈αthe␈αcommon␈αsense␈α
knowledge␈αimmediately␈αcalled␈αforth␈α
by␈αthe␈αstatement␈α
of␈αthe
␈↓ ↓H␈↓problem.␈α⊗ My␈α∃favorite␈α⊗example␈α∃of␈α⊗easy␈α∃creativity␈α⊗is␈α∃the␈α⊗following␈α⊗"checkerboard␈α∃covering
␈↓ ↓H␈↓problem":

␈↓ ↓H␈↓␈↓ α_"Two␈α
diagonally␈α
opposite␈α
corner␈αsquares␈α
are␈α
removed␈α
from␈αan␈α
8␈α
by␈α
8␈α
checkerboard.␈α The
␈↓ ↓H␈↓problem␈α⊂is␈α⊃whether␈α⊂the␈α⊂board␈α⊃can␈α⊂be␈α⊃covered␈α⊂with␈α⊂dominoes,␈α⊃each␈α⊂dominoe␈α⊂being␈α⊃a␈α⊂1␈α⊃by␈α⊂2
␈↓ ↓H␈↓rectangle capable of covering two adjacent squares".

␈↓ ↓H␈↓␈↓ α_The␈α⊂classical␈α⊂proof␈α⊂that␈α⊃the␈α⊂board␈α⊂cannot␈α⊂be␈α⊃covered␈α⊂requires␈α⊂noticing␈α⊂that␈α⊃a␈α⊂dominoe
␈↓ ↓H␈↓covers␈α∞two␈α∞squares␈α∞of␈α∞opposite␈α∞color,␈α∞but␈α∂since␈α∞the␈α∞deleted␈α∞squares␈α∞are␈α∞of␈α∞the␈α∞same␈α∂color,␈α∞there
␈↓ ↓H␈↓remain 32 squares of one color to be covered and only 30 of the opposite color.

␈↓ ↓H␈↓␈↓ α_Our␈α∀idea␈α∀is␈α∀that␈α∀this␈α∀proof␈α∀is␈α∪creative,␈α∀because␈α∀it␈α∀involves␈α∀introducing␈α∀an␈α∀idea␈α∪not
␈↓ ↓H␈↓apparently␈α∞relevant␈α∞to␈α∂the␈α∞statement␈α∞of␈α∞the␈α∂problem␈α∞-␈α∞namely,␈α∞the␈α∂colors␈α∞of␈α∞the␈α∞squares.␈α∂ To␈α∞a
␈↓ ↓H␈↓literate␈α
combinatorial␈α
mathematician,␈α
the␈α
problem␈αis␈α
easy,␈α
because␈α
parity␈α
arguments␈α
are␈αcommon
␈↓ ↓H␈↓in␈αcombinatorial␈αproblems,␈αand␈αhe␈αwill␈αquickly␈α
begin␈αto␈αlook␈αfor␈αsuch␈αan␈αargument.␈α
 Nevertheless,
␈↓ ↓H␈↓I␈α⊃want␈α⊃to␈α∩call␈α⊃the␈α⊃proof␈α⊃creative␈α∩-␈α⊃even␈α⊃if␈α⊃an␈α∩experienced␈α⊃combinatorist␈α⊃may␈α⊃not␈α∩get␈α⊃many
␈↓ ↓H␈↓creativity␈αpoints␈α
for␈αsuggesting␈α
it.␈α Getting␈α
computer␈αprograms␈αthat␈α
will␈αcome␈α
up␈αwith␈α
this␈αproof
␈↓ ↓H␈↓without␈α∞too␈α∞much␈α∂adhockery␈α∞won't␈α∞be␈α∂easy,␈α∞and␈α∞I␈α∂think␈α∞the␈α∞effort␈α∂will␈α∞provide␈α∞a␈α∂beginning␈α∞at
␈↓ ↓H␈↓deeper forms of creativity.

␈↓ ↓H␈↓␈↓ α_Here␈αis␈α
a␈αrelated␈α
problem␈αthat␈α
can␈αbe␈α
solved␈αby␈α
similar␈αmethods.␈α
 "Prove␈αthat␈α
a␈α3␈α
by␈α3␈αby␈α
3
␈↓ ↓H␈↓cube␈αcannnot␈αbe␈αtraversed␈αby␈αa␈αpath␈αthat␈αgoes␈αthrough␈αfaces␈αof␈αthe␈αsubcubes,␈αvisits␈αeach␈αsubcube
␈↓ ↓H␈↓exactly␈α
once,␈α
and␈α
ends␈α
in␈α
the␈α
middle␈α
subcube".␈α∞ Some␈α
like␈α
to␈α
regard␈α
it␈α
as␈α
a␈α
problem␈α
of␈α∞a␈α
worm
␈↓ ↓H␈↓eating␈αits␈αway␈αthrough␈αa␈αbarrel␈αof␈α27␈αapples␈αarranged␈αin␈αa␈αcubical␈αway.␈α This␈αone␈αinvolves␈αsome
␈↓ ↓H␈↓creativity even for someone who knows the solution of the checkerboard problem.

␈↓ ↓H␈↓␈↓ α_Three␈αother␈αsolutions␈α
of␈αthe␈αcheckerboard␈αproblem␈α
have␈αsome␈αinterest.␈α
 Shmuel␈αWinograd
␈↓ ↓H␈↓of␈α⊂IBM's␈α⊃Thomas␈α⊂J.␈α⊂Watson␈α⊃Research␈α⊂Center␈α⊂proposed␈α⊃the␈α⊂following␈α⊃"non-creative"␈α⊂solution.
␈↓ ↓H␈↓The␈αnumber␈α
of␈αvertical␈α
dominoes␈αprojecting␈α
from␈αthe␈αfirst␈α
row␈αinto␈α
the␈αsecond␈α
must␈αbe␈αodd,␈α
since
␈↓ ↓H␈↓one␈α
square␈αis␈α
missing␈α
and␈αa␈α
horizontal␈αdominoe␈α
takes␈α
up␈αan␈α
even␈αnumber␈α
of␈α
squares.␈α Likewise
␈↓ ↓H␈↓the␈α
number␈αprojecting␈α
from␈αthe␈α
second␈αrow␈α
to␈α
the␈αthird␈α
must␈αbe␈α
odd,␈αand␈α
so␈αforth␈α
down␈α
to␈αthe
␈↓ ↓H␈↓number␈αof␈αdominoes␈αprojecting␈αfrom␈αthe␈αseventh␈αrow␈αto␈αthe␈αeighth.␈α Therefore,␈αthe␈αtotal␈αnumber
␈↓ ↓H␈↓of␈αvertical␈αdominoes␈αis␈αthe␈α
sum␈αof␈αseven␈αodd␈αsummands␈αand␈α
therefore␈αmust␈αbe␈αodd.␈α By␈αa␈α
similar
␈↓ ↓H␈↓argument,␈αthe␈αnumber␈αof␈αhorizontal␈αdominoes␈αmust␈αbe␈αodd.␈α Thus␈αthe␈αtotal␈αnumber␈αof␈αdominoes
␈↓ ↓H␈↓is␈α
the␈αsum␈α
of␈αtwo␈α
odd␈αnumbers␈α
and␈αmust␈α
be␈αeven.␈α
 But␈αthis␈α
number␈αis␈α
31.␈α In␈α
spite␈αof␈α
Winograd's
␈↓ ↓H␈↓contention,␈α
I␈α
think␈α
this␈α
proof␈α
must␈α∞be␈α
regarded␈α
as␈α
creative,␈α
because␈α
it␈α
involves␈α∞introducing␈α
new
␈↓ ↓H␈↓ways of adding up the number of dominoes.
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓␈↓ α_Marvin␈αMinsky␈α
of␈αthe␈α
M.I.T.␈αArtificial␈α
Intelligence␈αLaboratory␈α
proposed␈αa␈α
different␈αproof
␈↓ ↓H␈↓based␈α⊃on␈α⊃dividing␈α⊃the␈α⊃board␈α⊃into␈α⊃parallel␈α⊃diagonals␈α⊃starting␈α⊃with␈α⊃a␈α⊃diagonal␈α⊃containing␈α⊃two
␈↓ ↓H␈↓squares␈α
adjacent␈αto␈α
one␈αof␈α
the␈αdeleted␈α
squares.␈α Clearly␈α
two␈αdominoes␈α
project␈αfrom␈α
the␈α2-square
␈↓ ↓H␈↓diagonal␈α⊃to␈α⊂the␈α⊃3-diagonal.␈α⊂ So␈α⊃one␈α⊃projects␈α⊂from␈α⊃the␈α⊂3-diagonal␈α⊃to␈α⊂the␈α⊃4-diagonal,␈α⊃hence␈α⊂3
␈↓ ↓H␈↓project␈α
from␈α
the␈α4-diagonal␈α
to␈α
the␈α5-diagonal,␈α
2␈α
from␈α5␈α
to␈α
6,␈α4␈α
from␈α
6␈αto␈α
7,␈α
and␈α3␈α
from␈α
7␈α
to␈α8.
␈↓ ↓H␈↓Starting␈α∂at␈α∞the␈α∂opposite␈α∞corner␈α∂we␈α∂also␈α∞get␈α∂3␈α∞from␈α∂7␈α∞to␈α∂8,␈α∂covering␈α∞only␈α∂six␈α∞squares␈α∂of␈α∂the␈α∞8-
␈↓ ↓H␈↓diagonal.␈α∞ Minsky's␈α∞proof␈α∞gets␈α∞more␈α
non-creativity␈α∞points,␈α∞because␈α∞it␈α∞applies␈α
only␈α∞to␈α∞the␈α∞8␈α∞by␈α
8
␈↓ ↓H␈↓checkerboard,␈α
and␈αone␈α
could␈α
wonder␈αwhether␈α
it␈α
would␈αalso␈α
work␈αfor␈α
a␈α
10␈αby␈α
10␈α
board,␈αwhereas
␈↓ ↓H␈↓the␈α
standard␈αproof␈α
and␈αWinograd's␈α
proof␈αobviously␈α
extend␈αto␈α
any␈αboards␈α
with␈αan␈α
even␈αnumber
␈↓ ↓H␈↓of␈α
squares␈α
on␈α
an␈α
edge.␈α
 Actually␈α
Minsky's␈α
argument␈α
can␈α
be␈α
generalized␈α
to␈α
an␈α
arbitrary␈αboard,␈α
and,
␈↓ ↓H␈↓if␈α∂we␈α∂like,␈α∂we␈α∂can␈α∂regard␈α∂the␈α∂generalization␈α∂as␈α∂a␈α∂metamathematical␈α∂argument␈α∂that␈α∂the␈α∂Minsky
␈↓ ↓H␈↓technique will give a special proof for any size board.

␈↓ ↓H␈↓␈↓ α_The␈α
next␈α
class␈α
of␈α
proofs␈α
is␈α
due␈α
to␈α
D.␈α
Stefanyuk␈α
of␈α
the␈α
Institute␈α
of␈αInformation␈α
Transmission
␈↓ ↓H␈↓Problems␈α∞in␈α∂Moscow.␈α∞ Stefanyuk␈α∞starts␈α∂by␈α∞labelling␈α∞an␈α∂arbitrary␈α∞square␈α∞on␈α∂the␈α∞board␈α∂with␈α∞the
␈↓ ↓H␈↓number␈α⊃1,␈α⊃labelling␈α⊃its␈α⊃neighbors␈α⊂2,␈α⊃labelling␈α⊃their␈α⊃neighbors␈α⊃3,␈α⊂etc.␈α⊃ We␈α⊃then␈α⊃note␈α⊃that␈α⊂one
␈↓ ↓H␈↓dominoe␈αprojects␈αfrom␈αthe␈α1-square␈αinto␈αthe␈α2-squares.␈α How␈αmany␈αproject␈αfrom␈α2-squares␈αto␈α3-
␈↓ ↓H␈↓squares␈α
depends␈α
on␈α
where␈α
we␈α
are␈α
in␈α
relation␈α
to␈α
the␈α
edge␈α
and␈α
corners␈α
of␈α
the␈α
board,␈α
but␈α
for␈α
any
␈↓ ↓H␈↓initial␈αsquare␈αit␈αcan␈αbe␈αfigured␈αout.␈α Proceeding␈αfrom␈α2-squares␈αto␈α3-squares,␈αetc.,␈αwe␈αcan␈αhope␈αto
␈↓ ↓H␈↓arrive␈α⊗at␈α⊗a␈α⊗contradiction␈α⊗at␈α⊗the␈α⊗end.␈α⊗ Experience␈α⊗shows␈α⊗that␈α⊗we␈α⊗always␈α⊗do␈α⊗arrive␈α↔at␈α⊗a
␈↓ ↓H␈↓contradiction,␈α⊗so␈α⊗that␈α⊗Stefanyuk␈α↔has␈α⊗found␈α⊗a␈α⊗whole␈α↔family␈α⊗of␈α⊗proofs␈α⊗that␈α↔the␈α⊗mutilated
␈↓ ↓H␈↓checkerboard␈α∂can't␈α∂be␈α∂covered.␈α∂ However,␈α∂he␈α⊂hasn't␈α∂proved␈α∂that␈α∂the␈α∂method␈α∂will␈α⊂always␈α∂work,
␈↓ ↓H␈↓although everyone believes it will always work.

␈↓ ↓H␈↓␈↓ α_Stefanyuk's␈α
proofs␈αand␈α
Minsky's␈α
proof␈αhave␈α
a␈α
common␈αgeneralization.␈α
 Namely,␈α
take␈αany␈α
set
␈↓ ↓H␈↓of␈αsquares␈αall␈αof␈αthe␈αsame␈αcolor,␈αlabel␈αthem␈α1,␈αand␈αcontinue␈αas␈αbefore.␈α Namely,␈αcount␈αthe␈αnumber
␈↓ ↓H␈↓that␈αmust␈αproject␈αfrom␈α
1-squares␈αto␈α2-squares,␈αand␈αhope␈α
to␈αarrive␈αat␈αa␈α
contradiction.␈α Stefanyuk
␈↓ ↓H␈↓starts␈α∞from␈α∞an␈α∞arbitrary␈α∞single␈α∞square␈α∞and␈α
Minsky␈α∞starts␈α∞from␈α∞the␈α∞four␈α∞squares␈α∞adjacent␈α∞to␈α
the
␈↓ ↓H␈↓deleted squares.

␈↓ ↓H␈↓␈↓ α_We␈αcan␈αshow␈αthat␈αthese␈αproofs␈αwill␈αalways␈αwork␈αby␈αgoing␈αback␈αto␈αa␈αcolor␈αargument.␈α Since
␈↓ ↓H␈↓we␈α
start␈α
with␈αsquares␈α
of␈α
a␈αthe␈α
1-squares␈α
are␈αof␈α
a␈α
single␈αcolor,␈α
the␈α
2-squares␈αwill␈α
be␈α
of␈αthe␈α
opposite
␈↓ ↓H␈↓color,␈α
etc.␈α
 Therefore,␈αa␈α
dominoe␈α
can␈αnever␈α
be␈α
placed␈αwithin␈α
the␈α
␈↓↓n␈↓-squares␈αfor␈α
any␈α
particular␈α␈↓↓n␈↓.
␈↓ ↓H␈↓(If␈αthe␈α1-squares␈αaren't␈αof␈αone␈αcolor,␈αthis␈αcan␈αhappen).␈α Now␈αcount␈αthe␈α␈↓↓n␈↓-squares␈αfor␈αodd␈α␈↓↓n␈↓,␈αand
␈↓ ↓H␈↓the␈α∂␈↓↓n␈↓-squares␈α∂for␈α∂even␈α∂␈↓↓n␈↓␈α∂separately.␈α∂ Each␈α∂group␈α∞consists␈α∂of␈α∂all␈α∂the␈α∂squares␈α∂of␈α∂one␈α∂color,␈α∞and
␈↓ ↓H␈↓therefore␈αone␈αgroup␈αhas␈α32␈αsquares␈αand␈αthe␈αother␈α30.␈α But␈αif␈αthe␈αnumbers␈αof␈αdominoes␈α
projecting
␈↓ ↓H␈↓from␈α
the␈α∞␈↓↓n␈↓-squares␈α
to␈α∞the␈α
␈↓↓n+1␈↓-squares␈α∞were␈α
to␈α
work␈α∞out,␈α
the␈α∞numbers␈α
of␈α∞squares␈α
of␈α∞each␈α
color
␈↓ ↓H␈↓would␈αhave␈αto␈αbe␈αthe␈αsame.␈α It␈αis␈αtempting␈αto␈αask␈αwhether␈αthe␈αmethod␈αcan␈αbe␈αfurther␈αgeneralized
␈↓ ↓H␈↓to include the Winograd proof.

␈↓ ↓H␈↓␈↓ α_The␈α∂purpose,␈α∞besides␈α∂entertainment,␈α∞of␈α∂presenting␈α∞all␈α∂these␈α∞proofs␈α∂is␈α∞to␈α∂provide␈α∂food␈α∞for
␈↓ ↓H␈↓thought␈α
concerning␈α
the␈α
problem␈α
of␈α
making␈α
computers␈α
creative.␈α
 It␈α
appears␈α
possible␈α∞though␈α
very
␈↓ ↓H␈↓difficult␈αto␈αmake␈αa␈αcomputer␈αprogram␈αthat␈αwould␈αcome␈αup␈αwith␈αall␈αthese␈αproofs.␈α Since␈αno␈αone␈αof
␈↓ ↓H␈↓these␈α
mathematicians␈α
found␈α
all␈α
of␈α
them,␈α
it␈α
would␈α
be␈α
a␈α
substantial␈α
achievement.␈α
 My␈α∞intuition␈α
is
␈↓ ↓H␈↓that such a program would tell us something more about creativity.

␈↓ ↓H␈↓2. ␈↓αGenerality␈↓

␈↓ ↓H␈↓3. ␈↓αPattern matching and higher order patterns␈↓
␈↓ ↓H␈↓␈↓ εH␈↓ 92


␈↓ ↓H␈↓4. ␈↓αLearning from experience␈↓

␈↓ ↓H␈↓5. ␈↓αTree search␈↓

␈↓ ↓H␈↓6. ␈↓αThe frame problem␈↓

␈↓ ↓H␈↓7. ␈↓α The qualification problem and minimal reasoning␈↓

␈↓ ↓H␈↓8. ␈↓αVagueness and fuzziness␈↓

␈↓ ↓H␈↓9. ␈↓αCausality and ability␈↓

␈↓ ↓H␈↓10. ␈↓αObjects and substances in space and time␈↓

␈↓ ↓H␈↓11. ␈↓αSelf-consciousness␈↓

␈↓ ↓H␈↓␈↓ α_What␈α⊃must␈α∩an␈α⊃intelligent␈α∩program␈α⊃know␈α∩about␈α⊃itself␈α∩and␈α⊃its␈α∩mental␈α⊃states␈α∩and␈α⊃mental
␈↓ ↓H␈↓processes?  How does it relate to what humans know about their own mental states and processes?

␈↓ ↓H␈↓12. ␈↓αMotivational structure␈↓

␈↓ ↓H␈↓␈↓ α_What␈α∞motivational␈α
structures␈α∞shall␈α
we␈α∞give␈α∞our␈α
programs,␈α∞and␈α
how␈α∞do␈α
these␈α∞relate␈α∞to␈α
the
␈↓ ↓H␈↓motivational␈α∞structures␈α∞of␈α
humans.␈α∞ I␈α∞will␈α
argue␈α∞that␈α∞the␈α
motivational␈α∞structures␈α∞of␈α∞humans␈α
are
␈↓ ↓H␈↓not␈α∂related␈α∂merely␈α∂to␈α∞problem␈α∂solving␈α∂ability,␈α∂and␈α∞it␈α∂will␈α∂not␈α∂be␈α∞to␈α∂our␈α∂advantage␈α∂to␈α∞construct
␈↓ ↓H␈↓intelligent␈α⊗computer␈α⊗programs␈α⊗with␈α⊗human-like␈α⊗motivational␈α⊗structures.␈α⊗ They␈α↔mightn't␈α⊗be
␈↓ ↓H␈↓obedient, and we might be motivated to ascribe to them rights and duties.

␈↓ ↓H␈↓␈↓ α_We␈α
can␈α
immediately␈α
mention␈α
two␈α∞characteristics␈α
of␈α
human␈α
motivation␈α
that␈α
we␈α∞won't␈α
want
␈↓ ↓H␈↓machines␈α⊂to␈α⊂have.␈α∂ First,␈α⊂our␈α⊂ideas␈α∂of␈α⊂what␈α⊂are␈α∂worthwhile␈α⊂lifetime␈α⊂goals␈α∂are␈α⊂affected␈α⊂by␈α∂our
␈↓ ↓H␈↓immediate chemical state.  In particular, fatigue affects long term goal structure.

␈↓ ↓H␈↓␈↓ α_Second,␈αin␈α
humans␈αsubgoals␈αoften␈α
acquire␈αa␈α
force␈αindependent␈αof␈α
the␈αgoals␈α
that␈αgave␈αrise␈α
to
␈↓ ↓H␈↓them.␈α∞ Thus␈α
behavioral␈α∞psychology␈α
suggests␈α∞that␈α∞goals␈α
are␈α∞adopted␈α
to␈α∞secure␈α∞parental␈α
approval.
␈↓ ↓H␈↓However, such goals often are pursued even when they lead to subsequent parental disapproval.

␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Artificial Intelligence Laboratory
␈↓ ↓H␈↓Computer Science Department
␈↓ ↓H␈↓Stanford University
␈↓ ↓H␈↓Stanford, California 94305

␈↓ ↓H␈↓ARPANET: MCCARTHY@SU-AI

␈↓ ↓H␈↓␈↓εThis draft of

␈↓ ↓H␈↓εPUBbed at 16:01 on June 16, 1977.␈↓